import com.sun.source.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-04
 * Time:22:19
 */
public class BinaryTree {
    static class TreeNode {
        //创建二叉树节点
        public char val;
        public TreeNode left; //存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建二叉树（不是真正的创建方式）
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }

    //前序遍历(递归遍历思路/子问题思路)
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //前序遍历 - 保存前序遍历的结果方式（遍历思路）注意该方法没有用到返回值，直接全部存储到同一个list中
    List<Character> list = new ArrayList<>();
    public void preorderTraversal1(TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);
    }
    //前序遍历 - 保存前序遍历的结果方式（子问题思路）应用返回值，每个递归都有自己的list存储数据
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list1 = new ArrayList<>();
        if (root == null) return list1;
        list1.add(root.val);

        List<Character> leftTree = preorderTraversal(root.left);
        list1.addAll(leftTree);

        List<Character> rightTree = preorderTraversal(root.right);
        list1.addAll(rightTree);

        return list1;
    }
    //二叉树前序非递归遍历实现
    //思路：使用stack栈实现。首先实例化Stack对象，使用cur引用接收root，当cur不等于null或者stack不为空时(一开始stack是空的，所以，要将
    //cur不为null的条件放在前面，即cur!=null || !stack.empty())，进入循环，当cur!=null时，再次进入循环，先将cur插入stack中，然后将cur
    //打印，cur往左子树走，即cur=cur.left；如果cur走到null，即左子树遍历结束，出循环，将栈中的栈顶元素出栈，用top引用接收该元素，然后开始遍历
    //cur的右子树，循环前面左子树时经过的路径。
    public void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //中序遍历 - 保存遍历结果
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list2 = new ArrayList<>();
        if (root == null) {
            return list2;
        }
        List<Character> leftTree = inorderTraversal(root.left);
        list2.addAll(leftTree);

        list2.add(root.val);

        List<Character> rightTree = inorderTraversal(root.right);
        list2.addAll(rightTree);

        return list2;
    }
    //二叉树中序非递归遍历实现
    public void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //后序遍历 - 保存遍历结果
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list3 = new ArrayList<>();
        if (root == null) {
            return list3;
        }
        List<Character> leftTree = postorderTraversal(root.left);
        list3.addAll(leftTree);

        List<Character> rightTree = postorderTraversal(root.right);
        list3.addAll(rightTree);

        list3.add(root.val);

        return list3;
    }
    //二叉树后序非递归遍历实现
    //与前序和中序遍历大致相同，只不过，要注意的是，后序遍历是左子树-右子树-根的遍历顺序，也就是说，遇到根节点先不可以打印，当遍历左子树的部分时，即
    //往cur的左子树走时，left走到null时，出循环，先获取一下栈的栈顶元素top(cur)，如果top的右子树right也为null，则说明top是
    //叶子节点(此时为左子树中的叶子节点),将top的值打印,将该栈顶元素出栈；如果right不为null，则往cur的右子树走，重复cur的left走过的路径。
    public void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        TreeNode prev = null;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }

    //二叉树的基本操作：
    //获取树中节点的个数 - 遍历二叉树，只要root不为空就++；整棵树有多少个节点=左子树的节点+右子树的节点+root(root根 即为1)
    public static int nodeSize = 0;
    public void size(TreeNode root) {
        if (root == null) {
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }
    //子问题思路 - 整棵树的节点=左子树的节点+右子树的节点+root
    public int size1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size1(root.left)+size1(root.right)+1;
    }

    //获取叶子节点的个数 - 整棵树的叶子节点=左子树的叶子+右子树的叶子
    //当一个根节点root的左子树和右子树都为空时，就是叶子节点，即root.left==null && root.right==null
    public static int leafSize;
    public void getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    //子问题思路
    public int getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    //获取第K层节点的个数 - root左子树的第k-1层 + root右子树的第k-1层（记住是递归思路）
    public static int kSize;
    public void getKLevelNodeCount(TreeNode root,int k) {
        if (root == null) {
            return;
        }
        if (k == 1) {
            kSize++;
        }
        getKLevelNodeCount(root.left,k-1);
        getKLevelNodeCount(root.right,k-1);
    }
    //子问题思路
    public int getKLevelNodeCount1(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount1(root.left,k-1) + getKLevelNodeCount1(root.right,k-1);
    }

    //获取二叉树的高度 - 左子树的高度和右子树的高度的最大值+1（分别求左子树的高度和右子树的高度）
    //子问题思路
    //时间复杂度：O(N)
    //空间复杂度：O(log_2N) - 最大高度(最好情况-平衡二叉树(最好是完全二叉树)-对于树中的任意节点，其左子树和右子树的高度差不超过1)
    public int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getTreeHeight(root.left);
        int rightHeight = getTreeHeight(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
        //return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    //检测值为value的元素是否存在 - 遍历二叉树(使用前序遍历)
    //有四种情况：
    //1.根节点的值是value  2.如果1不是，判断左子树  3.如果2不是，判断右子树  4.如果都不是，说明二叉树中无该值
    public TreeNode findVal(TreeNode root,char value) {
        if (root == null) {
            return null;
        }

        if (root.val == value) {
            return root;
        }

        TreeNode leftTree = findVal(root.left,value);
        if (leftTree != null) {
            return leftTree;
        }

        TreeNode rightTree = findVal(root.right,value);
        if (rightTree != null) {
            return rightTree;
        }

        return null;
    }

    //层序遍历
    //思路；使用队列解决问题 - 当cur不等于null，即二叉树不为空时，将root存在在队列中；
    //当队列不为空时，定义一个引用cur将树的根节点root赋值给cur，每次将队头的元素出队，然后将该元素打印出来，这个元素其实就是实时的root/cur根节点，
    //如果该root的左子树节点left不为null，则将这个左子树节点存放到队列中，接着该root的右子树节点right如果不为null，继续将这个右子树节点存放到
    //队列中，此时的队列还是不为空，继续将队列的队头元素root出队，打印该元素，重复上述操作，
    //将此时的出队的队头元素的left入队，right入队(不为null时)。直到二叉树层序遍历打印完成，结束循环。
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    //层序遍历 - 保存遍历结果 - 使用列表式的二维数组存储
    //给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
    //输入：root = [3,9,20,null,null,15,7]
    //输出：[[3],[9,20],[15,7]]
    //思路：只需要改变上面一种方法的一处，就是在每次打印节点值的部分，改成将节点值存放在二维列表的列表中，具体做法：
    //每次将root存放到队列后，求队列的长度size，size是多大，就将多少个节点值存放到二维列表中，在新的一轮将队头元素出队，将左子树节点和右子树节点
    //入队后，再次计算size，然后将size个节点值存放在新的二维列表的列表中，重复操作，直到全部节点都存放到二维列表中，返回该列表
    public List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Character> list = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    //判断一棵树是不是完全二叉树 - 使用队列解决问题
    //要知道队列中是可以存放null，这时候就要区分二叉树什么时候是空，什么时候是非空：如果队列中存放的是4个null，那么计算该队列的大小就是4，说明
    //队列存放null是可以的，不代表队列是空；如果队列中什么都没有，即没有存放null或者其他有效的元素，这时候才是真正的空。
    //思路：按照层序遍历的方式，将所有节点存放到队列中，期间定义一个cur引用接收出队列的队头元素，由于完全二叉树的性质，知道最终所有元素出对后，
    //队列中的元素只会剩下null，这就表示该树是一颗完全二叉树，如果剩下的元素有null又不是null的元素，表示不是完全二叉树。具体思路：
    //当二叉树为空时，将其视为是一个完全二叉树。每次将root存放到队列中，当队列不为空时，进入循环，定义一个cur引用，将
    //队头元素root出队列，cur接收这个结果，如果每次cur接收到的元素不是null，则将cur的left和right存放到队列中，如果是null，则break跳出循环
    //此时判断队列中剩余的元素，当队列不为空时，进入循环，每次获取一下队列的队头元素，如果该元素等于null，将其出队列，然后继续循环，如果剩余元素
    //全部都出队列了，那说明剩余的元素都是null，二叉树是完全二叉树；如果在获取队头元素期间，发现该元素不等于null，那就说明剩下的元素不都是null，
    //说明二叉树不是完全二叉树，返回false。
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode peek = queue.peek();
            if (peek != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }
}
